清明 | 共享披萨与公平分割

想象一下，现在达美乐推出了一款新品披萨——“甜辣交响乐”（名字来自GPT4）。在这张披萨上，一半点缀着韩式炸鸡并搭配番茄辣椒酱，而另一半则带有夏威夷风味，洒满了菠萝。作为一名美食爱好者，你自然对此垂涎三尺，于是你在树洞随机挑选了一名幸运洞友，与之相约共享这顿美食。但是，你踏入店门时却发现，这名洞友是一位外国友人，而你并不能确定他是否来自意大利 （一般认为，意大利人对菠萝披萨深恶痛绝）。那么问题来了，你应该如何切分这张披萨，使得这次聚餐在令双方都满意的氛围中结束呢？

日常生活中类似的一幕，是公平分配理论（fair division）的一个绝佳范例。公平分配理论关心如何构建有效的算法，使得我们可以将一系列资源公平地分配给若干参与者。考虑到不同参与者可能对同一事物所拥有的价值产生不同的判断，如上例中，不同人对菠萝披萨的接受程度可能天差地别，因而公平分配理论的一个核心原则便是，一个最佳的分配方案应该由所有参与者共同参与决策，而非由某个局外人说了算。

在只涉及两名参与者时，存在一个简单而高效的分配方法，“划分并选择”（divide and choose，也被称为“切分并选择”, cut and choose, 或“我切你选”, I cut, you choose）。操作上，它与小朋友们分糖果的方式没有区别：一个人负责切分，而另一个人优先选择。这样的算法可以确保，每名参与者获得的部分对其价值至少占全部资源价值的一半^[1]。

回到开始的例子，假设你只关心自己能够分到的披萨面积，而并不在乎它带着菠萝还是鸡肉。对你来说，将披萨分为等面积的两半，就是你能做出的最好操作。假设你恰好将其切分为了不同口味的两份，而现在便轮到外国友人优先选择。如果他是一个纯粹的意大利人，毫无疑问会选择韩式炸鸡风味的一半，在他选择后，你别无选择，只能将剩下的一份，即夏威夷风味的另一半，收入囊中。对你来说，一半面积的披萨能够为你提供的价值恰好为整张披萨的一半；而对于外国友人来说，由于菠萝无法为其带来价值，其分到的一半对其的价值与整张披萨的价值相同。双方各取所需，完美解决！值得注意的是，由于两人不同的价值判断，在你获得了  披萨价值时，外国友人获得部分的价值占比超过了  （实际上是100%）。

当有三名或更多的参与者时，事情会变得略微复杂，但类似的思想可以推广为“单一分割者”（lone divider）算法。在此算法中，同样有一名“幸运儿”会成为分割者，他需要根据自己的价值判断将资源  等分，这名“幸运儿”的选择方式可以是任意的，虽然不同选择方式可能会带来不同的分割结果，但并不影响我们的结论。而后其他参与者便从中选择一份可以接受的，也即那些对其价值不少于全部资源价值的  的份额。在其他  位参与者挑选完毕后，剩下的一份便归于分割者。当然，如果多人有着共同的需求，需要引入额外的调整以保证每个人都满意。（关于其他  位参与者如何挑选，以及冲突时的额外调整机制，此处省略了许多细节，详细说明可以参考^[2]。）这样一来，每个人至少都能得到其应有的一份，也即至少获得  的价值。^[1][3]。

公平分割理论的应用绝不限于日常生活中的琐事。从家族遗产分割、公司股份分配到国家税收政策制订，从互联网信息流的优化、机场交通管理到天体观测资源的分配，只要涉及到有限资源的分配，公平分配理论都能为我们提供有趣的见解。不仅如此，对于那些让人头疼的群体任务（比如小组作业或是家务），公平分配理论也能提供一针见血的解决方案。如果想更深入地了解这一理论，以下两本经典书籍或许是不错的选择^[4][5]。

现在，当你需要在餐桌上帮人夹菜时，或许可以考虑展示一下公平分割的技巧了……

参考文献

[1] Steinhaus, H. (1948). The problem of fair division. Econometrica, 16, 101-104.

[2] https://www.coconino.edu/resources/files/pdfs/academics/arts-and-sciences/MAT142/Chapter_8_FairDivision.pdf

[3] Kuhn, H. W. (1967). On games of fair division. Essays in mathematical economics.

[4] Brams, S. J., & Taylor, A. D. (1996). Fair Division: From cake-cutting to dispute resolution. Cambridge University Press.

[5] Robertson, J., & Webb, W. (1998). Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press.

文 | 宋铭宇

图 | 朱成轩

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。